UOJ300【CTSC2017】吉夫特 <子集DP>

Problem

【CTSC2017】吉夫特

时间限制：
空间限制：
简单的题目，既是礼物，也是毒药。
设计了一道简单的题目，准备作为送给大家。
输入一个长度为的数列
问有多少个长度大于等于 2 的不上升的子序列满足

输出这个个数对取模的结果。

输入格式

第一行一个整数。
接下来行，每行一个整数，这行中的第行，表示。

输出格式

一行一个整数表示答案。

样例输入输出

样例一

Input

Output

样例二至样例九

见样例数据下载。

限制与约定

对于前的测试点，；
对于前的测试点，；
对于前的测试点，；
对于前的测试点，；
对于前的测试点，；
对于的测试点，。
所有的互不相同，也就是说不存在同时满足和。

下载

样例数据下载

标签：子集DP

Solution

由定理可以推得当且仅当，于是原题转为需要使，即是的子集。
显然有：令表示在后面接若干个满足条件的序列总数，那么对于值是当前的子集的所有位置，均有。直接做子集即可。

Code

#include <bits/stdc++.h>
#define MAX_A 233333
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, s, f[MAX_A+5];
int main() {
    read(n);
    for (int i = 1, x, t; i <= n; i++) {
        read(x), t = (f[x]+1)%P, (s += t) %= P;
        for (int y = x; y; y = (y-1)&x)
            (f[y] += t) %= P;
    }
    return printf("%d\n", s-n), 0;
}